package leetCode.solution;

import java.util.Arrays;

// arr[] 居民点 放置 num个邮局的最优问题
public class Code03_PostOfficeProblem {

	public static int minDis1(int[] arr, int num) {
		if (arr == null || arr.length < 2 || num < 1) {
			return 0;
		}
		int n = arr.length;
		int[][] record = getRecord(arr);
		int[][] dp = new int[n][num + 1];

		// 初始化第一列
		for (int i = 0; i < n; i++) {
			dp[i][1] = record[0][i];
		}
		for (int i = 1; i < n; i++) {
			for (int j = 2; j <= Math.min(i, num); j++) {
				dp[i][j] = record[0][i];
				// 0...k...i 中 枚举k...i 放置最后一个邮局的情况
				for (int k = i; k > 0; k--) { // 1 .... i
					dp[i][j] = Math.min(dp[i][j], dp[k - 1][j - 1] + record[k][i]);
				}
			}
		}
		return dp[n - 1][num];
	}

	// record[i][j] 放一个邮局的最小距离
	private static int[][] getRecord(int[] arr) {
		int n = arr.length;
		int[][] record = new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				record[i][j] = record[i][j - 1] + arr[j] - arr[(j + i) >> 1];
			}
		}
		return record;
	}

	// 四边形不等式优化dp中的枚举
	public static int minDis2(int[] arr, int num) {
		if (arr == null || arr.length < 2 || num < 1) {
			return 0;
		}
		int n = arr.length;
		int[][] record = getRecord(arr);
		int[][] dp = new int[n][num + 1];
		int[][] choose = new int[n][num + 1];

		// 初始化第一列
		for (int i = 0; i < n; i++) {
			dp[i][1] = record[0][i];
		}
		for (int i = 1; i < n; i++) {
			for (int j = Math.min(i, num); j >= 2; j--) {
				dp[i][j] = record[0][i];
				// 0...k...i 中 枚举k...i 放置最后一个邮局的情况
				int down = choose[i - 1][j];
				int up = j == Math.min(i, num) ? i : choose[i][j + 1];
				for (int k = Math.min(i, up); k >= Math.max(1, down); k--) {
					if (dp[k - 1][j - 1] + record[k][i] < dp[i][j]) {
						dp[i][j] = dp[k - 1][j - 1] + record[k][i];
						choose[i][j] = k;
					}
				}
			}
		}
		return dp[n - 1][num];
	}

	// 四边形不等式优化dp中的枚举  一维表 没行时重复利用
	public static int minDis3(int[] arr, int num) {
		if (arr == null || arr.length < 2 || num < 1) {
			return 0;
		}
		int n = arr.length;
		int[][] record = getRecord(arr);
		int[][] dp = new int[n][num + 1];
		int[] choose = new int[num + 1];

		// 初始化第一列
		for (int i = 0; i < n; i++) {
			dp[i][1] = record[0][i];
		}
		for (int i = 1; i < n; i++) {
			for (int j = Math.min(i, num); j >= 2; j--) {
				dp[i][j] = record[0][i];
				// 0...k...i 中 枚举k...i 放置最后一个邮局的情况
				int down = choose[j];
				int up = j == Math.min(i, num) ? i : choose[j + 1];
				for (int k = Math.min(i, up); k >= Math.max(1, down); k--) {
					if (dp[k - 1][j - 1] + record[k][i] < dp[i][j]) {
						dp[i][j] = dp[k - 1][j - 1] + record[k][i];
						choose[j] = k;
					}
				}
			}
		}
		return dp[n - 1][num];
	}

	// for test
	public static int[] getSortedArray(int len, int range) {
		int[] arr = new int[len];
		for (int i = 0; i != len; i++) {
			arr[i] = (int) (Math.random() * range);
		}
		Arrays.sort(arr);
		return arr;
	}

	// for test
	public static void printArray(int[] arr) {
		for (int i = 0; i != arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	// for test
	public static void main(String[] args) {
		int[] arr = { 1, 3, 8, 10, 12 };
		int num = 3;
		System.out.println(minDis1(arr, num));
		System.out.println(minDis2(arr, num));

		int times = 100; // test time
		int len = 1000; // test array length
		int range = 2000; // every number in [0,range)
		int p = 50; // post office number max
		long time1 = 0; // method1 all run time
		long time2 = 0;// method2 all run time
		long start = 0;
		long end = 0;
		int res1 = 0;
		int res2 = 0;
		for (int i = 0; i != times; i++) {
			int office = (int) (Math.random() * p) + 1;
			arr = getSortedArray(len, range);
			start = System.currentTimeMillis();
			res1 = minDis1(arr, office);
			end = System.currentTimeMillis();
			time1 += end - start;
			start = System.currentTimeMillis();
			res2 = minDis2(arr, office);
			end = System.currentTimeMillis();
			time2 += end - start;

			if (res1 != res2) {
				printArray(arr);
				break;
			}
			if (i % 10 == 0) {
				System.out.print(". ");
			}
		}
		System.out.println();
		System.out.println("method1 all run time(ms): " + time1);
		System.out.println("method2 all run time(ms): " + time2);

	}
}
